/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * 哈希表，这个空间复杂度是O(N)，但是相比下面的方法，执行的内存消耗反而更小
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    if (head === null || head.next === null) return null

    let headSet = new Set(),
        temp = head

    while (temp !== null) {
        if (headSet.has(temp)) {
            return temp
        } else {
            headSet.add(temp)
        }
        temp = temp.next
    }

    return null
};


/**
 * 快慢指针，这个空间复杂度是O(1)
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    if (head === null || head.next === null) return null

    let slow = head,
        fast = head

    while (slow !== null && fast !== null && fast.next !== null) {
        slow = slow.next
        fast = fast.next.next
        if (slow === fast) {
            // 主要是能算出来慢节点再走c步，头节点再走c布，都会到环开始的节点
            // 头结点到环开始的节点是a步，环开始的节点到相遇的节点是b步，相遇的节点到环开始的节点是c步
            // slow走了a+b步，fast走了a+n(b+c)+b步。a+n(b+c)+b=2(a+b)
            // 得出a=(n-1)(b+c)+c
            let point = head
            while (point !== slow) {
                point = point.next
                slow = slow.next
            }
            return point
        }
    }

    return null
};

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

let a = new ListNode(4)
a.next = new ListNode(1)
a.next.next = new ListNode(8)
a.next.next.next = new ListNode(4)
a.next.next.next.next = new ListNode(5)
a.next.next.next.next.next = a.next